package leet.ku._169;

import java.util.Arrays;

public class Solution {
	
	public int majorityElement(int[] nums) {
		int[] p = Arrays.copyOf(nums, nums.length);
		return quickFound(p, 0, p.length - 1, p.length / 2);
	}
	
	private int quickFound(int[] nums, int st, int ed, int pos) {
		if (st == ed)
			return nums[st];
		
		int i = st;
		int j = ed;
		int m = nums[(i + j) / 2];
		while (i <= j) {
			while (nums[i] < m)
				i++;
			while (nums[j] > m)
				j--;
			if (i <= j) {
				int tmp = nums[i];
				nums[i] = nums[j];
				nums[j] = tmp;
				i++;
				j--;
			}
		}
		
		if (pos <= j)
			return quickFound(nums, st, j, pos);
		else if (pos >= i)
			return quickFound(nums, i, ed, pos);
		else
			return nums[pos];
	}
}
